<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="EovoM" id="EovoM"><span data-lake-id="uea9124a8" id="uea9124a8">典型回答</span></h1>
  <p data-lake-id="ude436bbe" id="ude436bbe"><span data-lake-id="u589cf469" id="u589cf469"> <br></span><span data-lake-id="u068609d8" id="u068609d8">小顶堆（Min Heap）是一种特殊的二叉堆数据结构，它满足以下性质：对于堆中的任意节点i，其父节点的值小于等于节点i的值。换句话说，堆中的最小值总是位于堆的根节点上。</span></p>
  <p data-lake-id="u783a6e9b" id="u783a6e9b"><span data-lake-id="u929ac5d1" id="u929ac5d1">​</span><br></p>
  <p data-lake-id="u10f10abb" id="u10f10abb"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691221691011-5012e8f3-fcd6-49b0-8296-63df3b9224d3.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_22%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u3f3cc11a" id="u3f3cc11a"><br></p>
  <p data-lake-id="u7fcbefad" id="u7fcbefad"><span data-lake-id="ube7d4853" id="ube7d4853">小顶堆是一种二叉堆数据结构，它可以使用数组来实现。</span></p>
  <p data-lake-id="u32814229" id="u32814229"><br></p>
  <p data-lake-id="uf9a46899" id="uf9a46899"><br></p>
  <p data-lake-id="u02b31789" id="u02b31789"><span data-lake-id="u62b8c86f" id="u62b8c86f">小顶堆常用于解决与最小值相关的问题，所以在实际应用中非常的广泛，比如：</span></p>
  <p data-lake-id="u46a45ecb" id="u46a45ecb"><span data-lake-id="ua1e069a9" id="ua1e069a9">​</span><br></p>
  <p data-lake-id="u18e16fba" id="u18e16fba"><span data-lake-id="u85d644fe" id="u85d644fe">1、</span><strong><span data-lake-id="u9517f990" id="u9517f990">查找最小值</span></strong><span data-lake-id="u950b29f4" id="u950b29f4">，在一群数字中，查找最小值，可以利用小顶堆，小顶堆的根节点就是最小值。</span></p>
  <p data-lake-id="u6ffb17ce" id="u6ffb17ce" style="text-indent: 2em"><span data-lake-id="uc0bd623d" id="uc0bd623d">如：从10亿个数字中，取出最小的10个数</span></p>
  <p data-lake-id="u93322d40" id="u93322d40"><span data-lake-id="u6fba26ad" id="u6fba26ad">2、排序，小顶堆可以用于堆排序，可以把一个数组构建成小顶堆，那么就是实现了从小到大的排序。</span></p>
  <p data-lake-id="u372d5e57" id="u372d5e57"><span data-lake-id="u9bf39a70" id="u9bf39a70">3、</span><strong><span data-lake-id="uff17e6a5" id="uff17e6a5">定时器</span></strong><span data-lake-id="u26567949" id="u26567949">，在定时器的实现中，可以使用小顶堆来管理即将触发的定时事件。每个定时事件可以表示为一个包含触发时间戳的数据结构。从堆顶不断取出需要执行的定时任务即可。</span></p>
  <p data-lake-id="u114596b9" id="u114596b9"><span data-lake-id="u3ea421ba" id="u3ea421ba">4、Dijkstra算法：在最短路径问题中，Dijkstra算法使用优先级队列来选择当前最短路径的下一个节点，而小顶堆可以用作实现该优先级队列。</span></p>
  <p data-lake-id="u70e97adf" id="u70e97adf"><span data-lake-id="u31bbf933" id="u31bbf933">5、</span><strong><span data-lake-id="ubca8a2c2" id="ubca8a2c2">优先级队列</span></strong><span data-lake-id="u67b3021c" id="u67b3021c">：小顶堆可以用作优先级队列的底层数据结构，在O(log n)时间内进行插入和删除操作，O(1)时间内获取最小优先级元素。如Java 中的 PriorityQueue</span></p>
  <p data-lake-id="u5e64429d" id="u5e64429d"><span data-lake-id="u35d77b85" id="u35d77b85">​</span><br></p>
  <h1 data-lake-id="PQlDS" id="PQlDS"><span data-lake-id="u00a5ecd7" id="u00a5ecd7">扩展知识</span></h1>
  <p data-lake-id="u9bf7a5e6" id="u9bf7a5e6"><br></p>
  <h2 data-lake-id="q9oWz" id="q9oWz"><span data-lake-id="uf2e71fcb" id="uf2e71fcb">插入过程</span></h2>
  <p data-lake-id="u101dc43c" id="u101dc43c"><br></p>
  <p data-lake-id="u04457ed4" id="u04457ed4"><span data-lake-id="u9c81956d" id="u9c81956d">小顶堆的插入主要有两个步骤：</span></p>
  <ul list="u3855fa39">
   <li fid="u1f68e95b" data-lake-id="u666a7575" id="u666a7575"><span data-lake-id="ue1f5f59d" id="ue1f5f59d">1、将新元素添加到小顶堆的最后一个位置（数组的末尾）。</span></li>
   <li fid="u1f68e95b" data-lake-id="u888f3a17" id="u888f3a17"><span data-lake-id="u7f93d13e" id="u7f93d13e">2、执行"上浮"（Heapify Up）操作：将新插入的元素与其父节点进行比较。如果新元素的值比父节点的值小，则交换它们，并继续向上比较和交换，直到满足小顶堆的性质（即新元素的值不小于其父节点的值），或者到达堆的根节点。</span></li>
  </ul>
  <p data-lake-id="udc52452d" id="udc52452d"><span data-lake-id="uba0ac274" id="uba0ac274">​</span><br></p>
  <p data-lake-id="u71a43d17" id="u71a43d17"><span data-lake-id="u6b540d5f" id="u6b540d5f">加入有一个以下小顶堆，当我们插入一个元素3的时候。</span></p>
  <p data-lake-id="u4076ccff" id="u4076ccff"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691221693280-038af3d7-8b61-4113-91dc-6d00f4a6a3f3.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_22%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u055c0c20" id="u055c0c20"><br></p>
  <p data-lake-id="u8e656125" id="u8e656125"><span data-lake-id="u1f868c32" id="u1f868c32">将3添加到堆的最后位置：</span></p>
  <p data-lake-id="u914bedde" id="u914bedde"><span data-lake-id="u437357b3" id="u437357b3">​</span><br></p>
  <p data-lake-id="ua50ed9c1" id="ua50ed9c1"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691221804702-b4aa5e33-3469-4987-9c70-976aee9f0e7b.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u83b218c3" id="u83b218c3"><br></p>
  <p data-lake-id="ub1adfe14" id="ub1adfe14"><span data-lake-id="ue3cecbda" id="ue3cecbda">执行上浮操作，将3上浮到正确位置：</span></p>
  <p data-lake-id="ub2fb8111" id="ub2fb8111"><span data-lake-id="u3e973cdc" id="u3e973cdc">​</span><br></p>
  <p data-lake-id="u4a2f7a0d" id="u4a2f7a0d"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691221930269-0ee12701-8eda-495d-85ad-44005804af3c.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_51%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u2b19a713" id="u2b19a713"><br></p>
  <h2 data-lake-id="oHSdr" id="oHSdr"><span data-lake-id="u077a7ca4" id="u077a7ca4">删除过程</span></h2>
  <p data-lake-id="u7c51c3c6" id="u7c51c3c6"><span data-lake-id="uf49865b1" id="uf49865b1">小顶堆的删除主要有两个步骤：</span></p>
  <ul list="u8eed291f">
   <li fid="u21182667" data-lake-id="u263c4ece" id="u263c4ece"><span data-lake-id="u9f44cbf1" id="u9f44cbf1">1：将堆顶元素（最小值）删除，并用堆的最后一个元素（数组的最后一个元素）来替换它。</span></li>
   <li fid="u21182667" data-lake-id="u2fb47459" id="u2fb47459"><span data-lake-id="u7d64b106" id="u7d64b106">2：执行"下沉"（Heapify Down）操作：将新的根节点与其较小的子节点进行比较。如果新根节点的值比其子节点的值大，则交换它们，并继续向下比较和交换，直到满足小顶堆的性质（即新根节点的值不大于其子节点的值），或者到达叶子节点。</span></li>
  </ul>
  <p data-lake-id="uc6f0c86a" id="uc6f0c86a"><span data-lake-id="uc2ac8cee" id="uc2ac8cee">​</span><br></p>
  <p data-lake-id="u909e5ee8" id="u909e5ee8"><br></p>
  <p data-lake-id="u9257f0b8" id="u9257f0b8"><span data-lake-id="uef8a04a1" id="uef8a04a1">以下是删除3这个元素的过程：</span></p>
  <p data-lake-id="u72c8890e" id="u72c8890e"><span data-lake-id="udc73f76b" id="udc73f76b">​</span><br></p>
  <p data-lake-id="u2dc049f2" id="u2dc049f2"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691222304519-1983cbd8-141c-420f-92d2-7c63498d80fb.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_49%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ub4741732" id="ub4741732"><br></p>
  <p data-lake-id="u1a402613" id="u1a402613"><span data-lake-id="u122885f2" id="u122885f2">经过几轮下沉后：</span></p>
  <p data-lake-id="u6a323584" id="u6a323584"><br></p>
  <p data-lake-id="uf0ac8171" id="uf0ac8171"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1691222311287-a7750217-2ddb-45cd-879d-52f1483d0a9d.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
 </body>
</html>